A Generative Adversarial Network for Multi-View Network Embedding

简介

论文传送门

该论文针对多视图网络表示学习问题（multi-view network representation），即如何为多视图网络中的节点构建低维和信息留存的嵌入的问题，提出来基于生成对抗网络的多视图网络表示框架。来自于真实世界的应用的数据，往往可以用多视图网络表征，其中节点通过多种关系连接。举例来说，在Facebook， 两名用户可以具有朋友关系，入学同一所大学，喜欢或者不喜欢一条动态。一个简单的多视图网络如Figure 1所示。

相比较单视图网络，使用GAN在多视图网络上做表示学习需要克服一个关键的挑战：在单视图网络中，生成器只需要建模节点对之间的连接性，但在多视图网络中，需要建模的不仅是不同节点之间的连接性，还需要建模不同视图间节点之间的连接性。

问题定义

多视图网络被定义为$\mathcal{G} = (\mathcal{V}, \mathcal{E})$，其中$\mathcal{V}=\{v_1, v_2,\cdot\cdot\cdot,v_n \}$记为节点集合，$\mathcal{E}=\{\mathcal{E}^1, \mathcal{E}^2, \cdot\cdot\cdot, \mathcal{E}^k\}$描述了编码 $k$ 种关系类型的边集合。对于给定的关系类型 $l$ ，$\mathcal{E}^{(l)}=\{e_{ij}^{(l)}\}_{i,j=1}^n$ 表示节点 $v_i$ 和 $v_j$ 对应关系的出现。因此，$e_{ij}^{(l)}=1$指示节点 $v_i$ 和 $v_j$ 有一条关系 $l$ 的边，0则反之。我们使用$\mathcal{K}_{ij}=(e_{ij}^{(1)}, \cdot\cdot\cdot,e_{ij}^{(k)})$来表示多视图拓扑中$(v_i, v_j)$的连接性。多视图网络表示学习的目标是学习一个嵌入矩阵$\mathrm{X} \in \mathbb{R}^{n \times d}$, 即多视图网络的低维嵌入，其中$d \ll n $是嵌入的维度。

方法

Multi-view Generative Adversarial Network

不像被设计在单视图网络做嵌入的GAN，这种GAN只需要建模单个视图中节点的连接性，MEGAN需要捕捉的不仅有每一种视图中节点之间的连接性，还需要建模视图之间的关联性。为了达到这个目的，给定真实节点对的分布$(v_i, v_j) \sim p_{data}$， MEGAN由两个模块组成：一个负责生成（或者选择）一个负样本节点$v_c$，$v_i$与$v_c$之间的连接模式$\mathcal{K}_{ic}$与真实样本对之间的连接模式需要足够相似；一个判别器，负责区分真实样本对$(v_i, v_j)$和虚假样本对$(v_i, v_c)$（ps：这里有一点疑惑，判别器基于什么判断是真实还是虚假，因为都是原图中存在的节点对，已发邮件询问作者）。Figure2展示了MEGAN的架构。对于节点对$(v_1, v_2)$，生成器产生一个虚假节点$v_4$来形成一个节点对$(v_1, v_4)$来欺骗判别器，并且判别器被训练来区分输入的节点对是真实的还是虚假的。判别器和生成器互相博弈，当收敛时，我们可以学习到生成器用来产生多视图网络所产生的嵌入。在这种情景下，该学习的嵌入可以捕捉到每一种视图中节点之间的连接性，还有不同视图之间的关联性。

Multi-view Generator

该论文的多视图网络生成器的目标是（i）：生成能欺骗判别器的具有多视图连接性的虚假样本对；（ii）：学习一个能捕捉到多视图网络拓扑的嵌入。为此，作者设计的多视图生成器由两部分组成：一个融合生成器$G_f$和$k$个连接性生成器$G^{(l)}$。令$X \in \mathbb{R}^{n \times d}$为我们想要学习到的网络嵌入矩阵，我们可以获得节点$v_i$的嵌入$e_i^TX$，其中$e_i$是一个one-hot向量。融合生成器$G_f$首先融合节点$v_i$和节点$v_j$的表示，旨在捕捉$v_i$和$v_j$之间的关联性。我们使用$G_f(v_i,v_j;X,\theta_f)$记作融合后的表示，其中$\theta_f$是融合生成器的参数。然后，融合后的表示被用来计算每一种视图中节点对之间连接性$e_{ij}^{(l)}\, for \, l = 1, …., k$的概率。这可以形式化写为：

$$G(e_{ij}^{(1)},...,e_{ij}^{(k)}|v_i,v_j,\theta_G)=\prod_{l=1}^kG^{(l)}(e_{ij}^{(l)}|G_f(v_i,v_j;X,\theta_f);\theta^{(l)})$$

其中$G^{(l)}$是一个连接性生成器，在给定融合后的表示时，负责生成给定视图$l$中节点对之间的连接性，$\theta^{(l)}$是它的参数。多视图生成器的参数为$\theta_G=\{X, \theta_f, \theta^{(l),l=1,…,k}\}$。

为了欺骗判别器，对每一$(v_i,v_j)\sim p_{data]}$，其中$p_{data}$代表多视图连接性，然后从$G$中采样一个负样本节点，该节点与$v_i$的连接性相似于$(v_i, v_j)$的相似性，$\tilde{\mathcal{K}_{ic}} = \mathcal{K}_{ij}$，比如，$(v_i,v_c) \sim p_g$，$p_g$代表由生成器建模的分布。在实践中，作者选取具有最高概率的节点$v_c$:

$$\mathop{argmax}_{v_c \in \mathcal{V}}\prod_{l=1}^kG^{(l)}(e_{ic}^{(l)}=e_{ij}^{(l)}|v_i,v_j,G_f(v_i,v_j;X,\theta_f))$$

在公式（2）中负采样背后的动机是：如果$\tilde{\mathcal{K}_{ic}}$与正样本对$(v_i,v_j)$的连接性$\mathcal{K}_{ij}$一样，负样本节点对$(v_i,v_c)$就更可能欺骗连接性判别器。生成器$G$的目标是更新网络嵌入和其参数，这样生成器就有更高的机会生成能够欺骗判别器的负样本。ps:这里$v_c$需要经过生成器的前向传播。

Node pair Discriminator

判别器$D$的目标是将来自于多视图网络的正样本节点对和由生成器产生的负样本节点对区分开来，这样可以迫使生成器$G$更准确的拟合多视图网络的连接性的分布。为这一目标，对任意来自于真实数据的节点对，也就是$(v_i, v_j) \sim p_{data}$，判别器应该输出1，以为该采样的节点对是真实的。给定负样本节点对，判别器应该输出0。作者定义判别器D为输入样本对$(v_i,v_j)$的内积的sigmoid函数，如下所示：

$$D(v_i,v_j) = \frac{exp(d_i^T \cdot d_j)}{1+exp(d_i^T \cdot d_j)}$$

Efficient Negative Node Sampling

简而言之，为了减少计算复杂度，负样本节点不是遍历整个节点集合，而是从与$v_i$至少有一条边连接的节点中选取负样本节点。

Objective Function of MEGAN

Training Algorithm of MEGAN

结论

pass

思考

同属性网络表示学习一样，多视图网络表示学习也要整合来自于不同域的信息，这两种方法可以相互借鉴和启发。